package org.leetcode.middle.leetcode560;

import java.util.Arrays;

public class Solution
{
    public static void main(String[] args) {
        Solution solution = new Solution();
        int [] nums = {1};
        int i = solution.subarraySum5(nums, 0);
        System.out.println(i);
    }


    public int subarraySum5(int [] nums,int k){

        int count = 0;
        int n = nums.length;
        int [] preSum = new int[n+1];
        preSum[0]=0;
        for (int i = 1; i <=n; i++) {
            preSum[i]=preSum[i-1]+nums[i-1];
        }

        for (int left = 0; left <=n; left++) {
            for (int right = left+1; right <=n; right++) {
                if (preSum[right]-preSum[left]==k){
                    count++;
                }
            }
        }

        return count;
    }

    public int subarraySum3(int [] nums,int k){

        int count = 0;
        int n = nums.length;
        int [] preSum = new int[n+1];

        preSum[0]=0;
        for (int i = 1; i <=n ; i++) {
            preSum[i]=preSum[i-1]+nums[i-1];
        }

        for (int right = 0; right < n; right++) {
            for (int left = 0; left <=right; left++) {
                if (preSum[right+1]-preSum[left]==k) {
                    count++;
                }
            }
        }

        return count;
    }

    public int subarraySum2(int[] nums, int k)
    {

        int length =nums.length;

        int[] preSums = new int[length + 1];

        preSums[0]=0;

        int res = 0;

        for (int i = 0; i < length; i++) {
            preSums[i+1]=preSums[i]+nums[i];
        }

        for (int left = 0; left < length; left++) {
            for (int right = left; right < length; right++) {
                //  可以看作为 preSums[left]+k==preSums[right+1]
                //  表明在left到right+1 之间存在一个和为k的子数组
                if (preSums[right+1]-preSums[left]==k)
                {
                    res++;
                }
            }
        }

        return res;

    }



    //错误
    public int subarraySum(int[] nums, int k) {

        Arrays.sort(nums);

        int left = 0;
        int right = 0;

        int num =0;

        while (nums[right]<=k)
        {
            int total =nums[left]+nums[right];


            if (total>k)
            {
                left=right;
                right++;
            }

            if (total<k)
            {
                left++;
            }

            if (total==k || nums[right]==k)
            {
                num++;
                right++;
            }
        }
        return num;
    }


}
